#ifndef DFT_H_
#define DFT_H_

#define _USE_MATH_DEFINES
#include <cmath>
#include <complex>

// Checks whether number if power of two
bool IsPowerOfTwo(int n);

// Returns number of bits required for representation number from [0, n - 1]
int NumBits(int n);

// Reverses first num_bits bits in n
int ReverseBits(int n, int num_bits);

// Performs bit-reversed permutation in-place
void ReorderElements(std::complex<float>* x, int n);

// Performs naive DFT algorithm for O(n*n) time
void DftGold(const std::complex<float>* x, int n, std::complex<float>* y);

// Performs Cooley-Tukey FFT algorithm in-place for O(n*log(n)) time
void DftInplace(std::complex<float>* x, int n);

// Fills vector with uniformly distributed pseudo-random values from [low, high] range
void FillRandom(float low, float high, int n, std::complex<float>* x);

// Returns maximum per element relative error
float RelativeError(const std::complex<float>* gold, const std::complex<float>* mine, int n);

#endif // DFT_H_